home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 15404 < prev    next >
Encoding:
Text File  |  1996-08-05  |  1.2 KB  |  31 lines
  1. Newsgroups: comp.lang.c++
  2. Path: in2.uu.net!allegra!alice!ark
  3. From: ark@research.att.com (Andrew Koenig)
  4. Subject: Re: Can I do it recursively?
  5. Message-ID: <DpDDs4.3ut@research.att.com>
  6. Organization: AT&T Research, Murray Hill NJ
  7. References: <4juo6m$n6i@doc.zippo.com>
  8. Date: Fri, 5 Apr 1996 03:31:15 GMT
  9.  
  10. In article <4juo6m$n6i@doc.zippo.com> Clarence Chiang writes:
  11.  
  12. > I don't think it is a question of whether the problem can be solved recursively
  13. > or iteratively. It is just that this problem is one of those NP-complete problem,
  14. > which requires exponential amount of time as the problem size grows.
  15.  
  16. I wrote a program to do an 8x8 knight's tour somewhere around 1977.
  17. At the time it took about three minutes of cpu time on an IBM 360/91.
  18. That was a pretty big mainframe -- at one time it was the fastest
  19. general-purpose computer availble in the world.
  20.  
  21. By today's standards, it was about as fast as a cheap PC:
  22. its basic clock rate was only 16 MHz but it was capable of
  23. executing one complete instruction per clock cycle under good
  24. conditions.  Under typical conditions, it did about 5-10 MIPS.
  25.  
  26. So I would expect a solution to the problem today to run in
  27. a couple of minutes.  Not a big deal.
  28. -- 
  29.                 --Andrew Koenig
  30.                   ark@research.att.com
  31.